/**
 * 75. 颜色分类
 * https://leetcode-cn.com/problems/sort-colors/
 */
const { displayBaseArray } = require('../../libs/public');

function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function sortColors(nums) {
  let left = 0;
  while (left < nums.length && !nums[left]) {
    left += 1;
  }
  let right = nums.length - 1;
  while (right >= left && nums[right] === 2) {
    right -= 1;
  }
  let i = left;
  while (i <= right) {
    if (!nums[i]) {
      if (i > left) {
        swap(nums, i, left);
        left += 1;
        continue;
      }
    } else if (nums[i] === 2) {
      if (i < right) {
        swap(nums, i, right);
        right -= 1;
        continue;
      }
    }
    i += 1;
  }
}

let nums;

nums = [2, 0, 2, 1, 1, 0];
sortColors(nums);
console.log(displayBaseArray(nums) === '[0,0,1,1,2,2]');

nums = [2, 0, 1];
sortColors(nums);
console.log(displayBaseArray(nums) === '[0,1,2]');

nums = [0, 1, 0];
sortColors(nums);
console.log(displayBaseArray(nums) === '[0,0,1]');

nums = [1, 2, 0];
sortColors(nums);
console.log(displayBaseArray(nums) === '[0,1,2]');
